#include <iostream>
#include <vector>
using namespace std;

struct Node{
    Node* right;
    Node* down;
    int val;
    Node(Node *right, Node * down, int val) 
        :right(right), down(down), val(val){}
};

class Skiplist {
private:
    Node *head;
    const static int MAX_LEVEL = 32;
    vector<Node*> pathList;

public:
    Skiplist() {
        head = new Node(nullptr, nullptr, -1);
        pathList.reserve(MAX_LEVEL);
    }
    
    bool search(int target) {
        Node* p = head;
        while(p) {
            while(p->right && p->right->val < target) {
                p = p->right;
            }
            if(p->right && p->right->val == target) return true;
            else p = p->down;
        }        
        return false;
    }
    
    void add(int num) {
        pathList.clear();
        Node* p = head;
        while(p) {
            while(p->right && p->right->val < num) {
                p = p->right;
            }
            pathList.push_back(p);
            p = p->down;
        }
        bool insertUp = true;
        Node* downNode = nullptr;
        while(insertUp && pathList.size()) {
            Node *insert = pathList.back();
            pathList.pop_back();
            insert->right = new Node(insert->right, downNode, num);
            downNode = insert->right;
            insertUp = (rand() & 1) == 0;
        }
        if(insertUp) {
            head = new Node(new Node(nullptr, downNode, num), head, -1);
        }
    }
    
    bool erase(int num) {
        Node *p = head;
        bool seen = false;
        while(p) {
            while(p->right && p->right->val < num) {
                p = p->right;
            }
            if(p->right && p->right->val == num) {
                seen = true;
                p->right = p->right->right;
                p = p->down;
            }
            else p = p->down;
        }
        return seen;
    }
};

int main() {
    Skiplist st;
    st.add(1);
    st.add(2);
    st.add(3);
    st.add(4);
    st.add(8);
    cout << st.search(5) << endl;
    cout << st.search(4) << endl;
    return 0;
}